package com.linyaonan.leetcode.medium._1019;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 给定一个长度为 n 的链表 head
 *
 * 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
 *
 * 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
 *
 * 输入：head = [2,7,4,3,5]
 * 输出：[7,0,5,5,0]
 *
 *
 * 提示：
 *
 * 链表中节点数为 n
 * 1 <= n <= 10^4
 * 1 <= Node.val <= 10^9
 * @author: Lin
 * @date: 2024/10/10
 */
public class NextGreaterNodeInLinkedList {

    /**
     * 题目要求找到更大的节点，看到第一个，最大这些字眼需要想到使用单调栈
     *
     * 要求是链表节点后面中比自身大的最大的结果，按照数组进行分析一下
     *
     * [2,7,4,3,5]
     *
     * 我们从右向左分析
     *
     * 1. 5压栈
     * 2. 3忽略，因为3比5小，从左侧看更大的结果为5
     * 3. 4忽略，因为4比5小，从左侧看更大的结果为5
     * 4. 7压栈，5弹栈，从左侧看7结果更大
     * 5. 2忽略
     *
     * 最后结果为
     * [7,0,5,5,0]
     *
     * @param head
     * @return
     */
    public int[] nextLargerNodes(ListNode head) {
        // 1. 遍历一遍链表将结果存入集合中
        ArrayList<Integer> list = new ArrayList<>();

        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        int[] result = new int[list.size()];

        // 2. 从左向右遍历，使用单调栈
        LinkedList<Integer> queue = new LinkedList<>();
        LinkedList<Integer> index = new LinkedList<>();

        queue.addLast(list.get(0));
        index.addLast(0);

        for (int i = 1; i < list.size(); i++) {
            while (!queue.isEmpty() && queue.peekLast() < list.get(i)) {
                result[index.removeLast()] = list.get(i);
                queue.removeLast();
            }

            queue.addLast(list.get(i));
            index.addLast(i);
        }

        return result;

    }

}
